package vernhe;

import java.util.Comparator;

/**
 * 平衡二叉搜索树，抽取了旋转的操作，便于AVL树和红黑树重复利用
 */
public class BBST<E> extends BST<E>{
    public BBST() {
        this(null);
    }

    public BBST(Comparator<E> comparator) {
        super(comparator);
    }

    /**
     * 恢复平衡
     *
     *          r         r
     *        /            \
     *      d               d
     *    /   \           /   \
     *   b     f         b     f
     *  / \   / \       / \   / \
     * a   c e   g     a   c e   g
     *
     */
    protected void rotate(Node<E> r,
                        Node<E> a,Node<E> b,Node<E> c,
                        Node<E> d,
                        Node<E> e,Node<E> f,Node<E> g) {
        //更改当前字数的父节点的子节点
        d.parent = r.parent;
        if (r.isLeft()) {
            r.parent.left = d;
        }else if (r.isRight()) {
            r.parent.right = d;
        }else {
            root = d;
        }

        //a - b - c
        b.left = a;
        b.right = c;
        if (a != null) {
            a.parent = b;
        }
        if (c != null) {
            c.parent = b;
        }

        //e - f - g
        f.left = e;
        f.right = g;
        if (e != null) {
            e.parent = f;
        }
        if (g != null) {
            g.parent = f;
        }

        //b - d - f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
    }

    /**
     * 对传入的节点进行左旋转
     * @param grand
     */
    protected void rotateLeft(Node<E> grand){
        //获得节点的句柄
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        //更改这些节点的左右孩子
        grand.right = child;
        parent.left = grand;
        afterRotate(grand,parent,child);
    }

    /**
     * 对传入的节点进行右旋转
     * @param grand
     */
    protected void rotateRight(Node<E> grand){
        //获得节点的句柄
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        //更改节点的左右孩子
        grand.left = child;
        parent.right = grand;
        afterRotate(grand,parent,child);

    }

    /**
     * 替换grand parent child的父节点并更新grand parent的高度
     * @param grand
     * @param parent
     * @param child
     */
    protected void afterRotate(Node<E> grand,Node<E> parent,Node<E> child) {
        //更改parent的parent的指向
        parent.parent = grand.parent;
        //更改grand的parent的孩子节点
        if (grand.isLeft()) {
            grand.parent.left = parent;
        } else if (grand.isRight()) {
            grand.parent.right = parent;
        } else {
            //当grand为root的时候
            root = parent;
        }
        //更改child节点的parent
        if (child != null) {
            child.parent = grand;
        }
        //更改grand的parent
        grand.parent = parent;
    }
}
